
//802.找到最终的安全状态
class Solution {
public:
    vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
        //就是所有节点中没有指向的节点以及指向的全是终端节点的节点
        int n = graph.size();
        unordered_map<int,int> m; //存放每一个节点指向多少节点
        unordered_map<int,vector<int>> each;  //记录每个节点被那些节点所指向

        for(int i = 0; i < n; i++)
        {
            auto& nums = graph[i];
            if(nums.size()) m[i] = nums.size();
            for(auto& x : nums)
                each[x].push_back(i);
        }
        queue<int> q;  //记录没有被指向的节点
        for(int i = 0; i < n; i++)
            if(m.count(i)==0) q.push(i);
        vector<int> ret;
        while(q.size())
        {
            int sz = q.size();
            for(int k = 0; k<sz ; k++)
            {
                int f = q.front();
                q.pop();
                ret.push_back(f);
                auto& nums = each[f];
                for(auto& x :nums)
                    if(--m[x] == 0) 
                        q.push(x);   //已经没有指向的节点了,是终端节点
            }            
        }
        sort(ret.begin(),ret.end());
        return ret;
    }
};